package com.nowcoder.code.lcof;

import com.algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class JZ84 {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(0);
        treeNode.left = new TreeNode(1);
        System.out.println(new JZ84().FindPath(treeNode, 1));
    }

    int size = 0;
    int sum;
    List<Integer> list = new ArrayList<>();

    public int FindPath(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        if (root.val == sum) {
            size++;
        }
        this.sum = sum;
        list.add(root.val);
        dfs(root.left,root.val);
        dfs(root.right, root.val);
        return size;

    }

    public void dfs(TreeNode treeNode, int s) {
        if (treeNode == null) {
            return;
        }

        int nowS = s = s + treeNode.val;
        if (nowS == sum) {
            size++;
        }
        for (Integer integer : list) {
            nowS = nowS - integer;
            if (nowS == sum) {
                size++;
            }
        }

        list.add(treeNode.val);
        dfs(treeNode.left, s);
        dfs(treeNode.right, s);
        list.remove(list.size() - 1);
    }

}
